package study;

import java.util.Arrays;

public class ReconstructQueue {

    // 还存在问题
    public static int[][] reconstructQueue(int[][] people) {
        int n = people.length;
        int[] sumArr = new int[n + 1];
        int[][] arr = new int[n + 1][2], ans = new int[n][2];
        System.arraycopy(people, 0, arr, 1, n);
        Arrays.sort(arr, 1, n + 1, (o1, o2) -> {
            if (o1[0] == o2[0])
                return o2[1] - o1[1];
            return o1[0] - o2[0];
        });

        for (int i = 2; i <= n; i++) {
            update(sumArr, i, 1);
        }
        for (int i = 1; i <= n; i++) {
            int k = arr[i][1];
            int l = 1, r = n;
            while (l < r) {
                int mid = l + r >> 1;
                if (sum(mid) >= k)
                    r = mid;
                else
                    l = mid + 1;
            }
            ans[r - 1] = arr[i];
            update(sumArr, r, -1);
        }
        return ans;
    }

    public static int lsb(int x) {
        return x & -x;
    }

    public static void update(int[] bit, int i, int c) {
        i++;
        while (i < bit.length) {
            bit[i] = bit[i] + c;
            i = i + lsb(i);
        }
    }

    public static int sum(int i) {
        int sum = 0;
        i++;
        while (i > 0) {
            sum = sum + i;
            i = i - lsb(i);
        }
        return sum;
    }

    public static void main(String[] args) {
        int[][] input = {{6, 0}, {5, 0}, {4, 0}, {3, 2}, {2, 2}, {1, 4}};
        int[][] ret1 = reconstructQueue(input);
        for (int i = 0; i < ret1.length; i++) {
            System.out.print(Arrays.toString(ret1[i]));
            System.out.print(" ");
        }
    }
}
